/*
 * Sorts.java
 * Autora: Jennifer Valdez
 * Carne: 10189
 * Fecha de entrega: 10 de agosto de 2011
 * Descripcion: clase que ordena un arreglo de enteros por medio de dos sorts
 *          y por medio de un profiler se miden los tiempo.
 */

// librerias importadas
import java.util.InputMismatchException;
import java.util.Random;
import java.util.Scanner;

public class Sorts {

    public static void main(String[] args) {
        
	//atributos
        int[] datos = new int[10];
        int[] datosOrdenados;
        Random random = new Random();
        
        //variables
        int opcion;
        int num;
        
        do{
            menu();
            opcion = pedirNumero("Ingrese la opcion");
            switch (opcion){
                case 1: // generar lista con numeros enteros al azar
                    //pide un numero positivo para el ingreso de cantidad de numeros a ordenar
                    do{
                            num = pedirNumero("Ingrese cantidad de datos a ordenar");
                    } while (num < 1);
                    datos = new int[num];
                    for (int i = 0; i < num; i++)
                            datos[i] = random.nextInt(100);   // se crean datos aleatorios entre 0 -100
                    desplegarDatos(datos);
                    break;
                case 2: // generar un arreglo con numeros ordenados
                    //pide un numero positivo para el ingreso de cantidad de numeros a crear
                    do{
                            num = pedirNumero("Ingrese cantidad de datos");
                    } while (num < 1);
                    datos = new int[num];
                    for (int i = 0; i< num; i++)
                            datos[i]=i*2;       // se crean datos ordenados 0, 2, 4, 6, ...
                    desplegarDatos(datos);
                    break;
                case 3: // ordena una lista por medio de InsertionSort
                    datosOrdenados = new int[datos.length]; 
                    datosOrdenados = insertionSort(datos, datos.length);  //INSERTIONSORT
                    System.out.println("\n Los datos han sido ordenados:");
                    desplegarDatos(datosOrdenados);
                    break;
                case 4: // ordena una lisata por medio de QuickSort   
                    datosOrdenados = new int[datos.length]; 
                    datosOrdenados = quickSort(datos, datos.length);   //QUICKSORT
                    System.out.println("\n Los datos han sido ordenados:");
                    desplegarDatos(datosOrdenados);
                    break;
                case 5: // salir del programa
                    System.out.println("\n .: Feliz dia :. \n");
                    break;
                default: // no selecciono ninguna opcion
                    System.out.println("\n ERROR -> esa opcion no existe \n");
                    break;
            } 
        }while (opcion != 5);
    }
    
    //menu: muestra en pantalla el menu principal para el usuario
    //no posee parametros y no devuelve ningun valor
    public static void menu(){
        System.out.println();
        System.out.println("+-------   MENU   -------------------+");
        System.out.println("| 1. Generar datos al azar           |");
        System.out.println("| 2. Generar datos ordenados         |");
        System.out.println("| 3. Ordenar con InsertionSort       |");
        System.out.println("| 4. Ordenar con QuickSort           |");
        System.out.println("| 5. Salir del programa              |");
        System.out.println("+------------------------------------+");
    }
    
    //desplegarDatos: despliega el conjunto de numeros
    public static void desplegarDatos(int[] data){
        for (int i = 0; i < data.length; i++)
        	System.out.print(data[i]+" ");
    }
    
    //pedirOpcion: pide el numero de la opcion ya validado
    //parametro tipo String que es la pregunta previa a que el usuario introduzca el numero
    //devuelve el entero con el valor
    public static int pedirNumero(String texto){
        Scanner readln = new Scanner(System.in);
        int numero = 0;
        try{
                System.out.println(texto);
                numero = readln.nextInt();
        }
        catch(InputMismatchException exception){
                System.out.println("\n ERROR --> NUMERO NO VALIDO \n");
        }
        readln.nextLine();
        return numero;
    }
    
    //insertionSort: ordena elementos colocando hasta el frente los numeros ya ordenados
    //	pre: 0 <= n <= data.length
    //	post: valores en datos[0..n-1] estan en orden acendente
    public static int[] insertionSort(int data[], int n){
    	int numSorted = 1;
    	int index;
    	while (numSorted < n){
    		//obtiene el primer valor no ordenado
    		int temp = data[numSorted];
    		// ... inserta dentro de los valores insertados
    		for (index = numSorted; index > 0; index--){
    			if (temp < data[index-1])
    				data[index] = data[index-1];
    			else
    				break;
    		}
    		// vuelve a ingresar el valor
    		data[index] = temp;
    		numSorted++;
    	}
    	return data;
    }
    
    // pre: left <= right
    // post: data[left] es colocada en el lugar correcto y regresa el lugar
    private static int partition(int data[], int left, int right){
         while (true){
                 // mueve el puntero derecho hacia la izquierda
                 while (left < right && data[left] < data[right]) right--;
                 if (left < right) swap(data,left++,right);
                 else return left;
                 // mueve el puntero izquierdo hacia derecha
                 while (left < right && data[left] < data[right]) left++;
                 if (left < right) swap(data,left,right--);
                 else return right;
         }
    }
    
    // post: los valores en data[0..n-1] estan en orden ascendente
    public static int[] quickSort(int data[], int n){
    	quickSortRecursive(data,0,n-1);
    	return data;
	}
    
    // pre: 0 <= i,j < data.length
    // post: data[i] y data[j] son intercambiados
    public static void swap(int data[], int i, int j){
    	int temp;
    	temp = data[i];
    	data[i] = data[j];
    	data[j] = temp;
    }
    
    // pre: left <= right
    // post: data[left..right] es orden ascendente
    private static void quickSortRecursive(int data[],int left,int right){
    	int pivot; // numero de pivote
		 if (left >= right) return;
		 pivot = partition(data,left,right); /* 1 - place pivot */
		 quickSortRecursive(data,left,pivot-1); /* 2 - sort small */
		 quickSortRecursive(data,pivot+1,right);/* 3 - sort large */
	 }
    
}
